Binary Search Tree III

樹主要有三種走訪的方式，分別是InOrder、PreOrder、PostOrder，主要差別在於走訪的順序

InOrder

走訪的順序為: [1,3,4,5,8,9,12]
它會按照值的大小走訪，如果你想知道樹有什麼值，用InOrder可以一目了然

PreOrder

走訪的順序為: [5,3,1,4,9,8,12]
它是從上到下的走訪，根節點開始，左節點走到底，再走右節點
當你要複製一顆樹，用PreOrder很適合，只要你照它輸出的順序去insert，就可以產生一樣的樹

PostOrder

走訪的順序為: [1,4,3,8,12,9,5]
它是從下到上的走訪，從左邊最底下的節點開始上去，再到右邊，最後才回到根節點

三種走訪的實作方式基本上是一樣～

程式:

func (t *BinarySearchTree) InOrder() {
	t.inOrderDFS(t.root)
}

func (t *BinarySearchTree) inOrderDFS(node *Node) {
	if node == nil {
		return
	}

	t.inOrderDFS(node.Left)
	fmt.Println(node.Val)
	t.inOrderDFS(node.Right)
}

func (t *BinarySearchTree) PreOrder() {
	t.preOrderDFS(t.root)
}

func (t *BinarySearchTree) preOrderDFS(node *Node) {
	if node == nil {
		return
	}

	fmt.Println(node.Val)
	t.preOrderDFS(node.Left)
	t.preOrderDFS(node.Right)
}

func (t *BinarySearchTree) PostOrder() {
	t.postOrderDFS(t.root)
}

func (t *BinarySearchTree) postOrderDFS(node *Node) {
	if node == nil {
		return
	}

	t.postOrderDFS(node.Left)
	t.postOrderDFS(node.Right)
	fmt.Println(node.Val)
}

func main() {
	tree := &BinarySearchTree{}
	tree.Insert(5)
	tree.Insert(3)
	tree.Insert(1)
	tree.Insert(4)
	tree.Insert(9)
	tree.Insert(8)
	tree.Insert(12)

	fmt.Println("InOrder:")
	tree.InOrder()
	fmt.Println("--------")

	fmt.Println("PreOrder:")
	tree.PreOrder()
	fmt.Println("--------")

	fmt.Println("PostOrder:")
	tree.PostOrder()
	fmt.Println("--------")
}

output:

InOrder:
1
3
4
5
8
9
12
--------
PreOrder:
5
3
1
4
9
8
12
--------
PostOrder:
1
4
3
8
12
9
5
--------

明天會講二元樹的刪除～